//
// Created by Administrator on 2022/2/20.
//

#ifndef CPP_LEARNING_MERGESORT_H
#define CPP_LEARNING_MERGESORT_H
#include <iostream>
using Rank = int;
//[lo, hi)
template <class T>
void copyFrom(T* newElem, T*oldElem, int len){
    for(int i=0;i<len;i++){
        newElem[i] = oldElem[i];
    }
}

template <class T>
void printElem(T* elem, Rank len){
    for(int i=0;i < len; i++){
        std::cout<<elem[i] << " " ;
    }
    std::cout<<std::endl;
}

//[lo, hi)
template <class T>
void mergeSort(T* elem, Rank lo, Rank hi){
    // 当元素个数为空或者仅有一个时， 直接返回
    if(hi <= lo + 1) return ;
    Rank mid = (lo + hi) /2;


    //std::cout<<"before mergeSort"<<std::endl;
    //printElem(elem, hi-lo);

    T* leftElems;
    T* rightElems;

    int leftNum = mid-lo;
    int rightNum = hi-mid;

    if(leftNum > 0){
        leftElems = new T[leftNum];
        copyFrom(leftElems, elem, leftNum);

        mergeSort(leftElems, lo, mid);

    }
    if(rightNum > 0){
        rightElems = new T[rightNum];
        copyFrom(rightElems, elem + mid , rightNum);

        mergeSort(rightElems, mid-mid, hi-mid);

    }

    // 归并  merge
    int l=0, r = 0;
    int i=lo;
    while (l < leftNum && r < rightNum){
        if(leftElems[l] <= rightElems[r]){
            elem[i++] = leftElems[l++];
        }else{
            elem[i++] = rightElems[r++];
        }
    }

    while (l < leftNum ){
        elem[i++] = leftElems[l++];
    }

    while (r < rightNum){
        elem[i++] = rightElems[r++];
    }

    if(leftNum > 0){
        delete [] leftElems;
    }
    if(rightNum > 0){
        delete [] rightElems;
    }

//    std::cout<<"after mergeSort"<<std::endl;
//    printElem(elem, hi-lo);
}


#endif //CPP_LEARNING_MERGESORT_H
